A technology for authenticating that predetermined information is stored in a specified or unspecified device (for example, in a storage such as a hard disc) is called message authentication technology. This technology is characterized in that a traffic volume required for an authentication process does not depend on an amount of information (an information volume) to be proved to be stored.
The outline of a conventional message authentication technology will be described below. A proving device and a verification device share a secret key k beforehand. Next, the proving device calculates a message authentication code M(s,k) having a fixed length for held information s and sends the message authentication code M(s,k) to the verification device. The verification device has a copy of the information s and verifies the correctness of the message authentication code M(s,k) having been sent from the proving device.
A message authentication code is designed by mainly using a technique related to common key cryptography and a hash function. Non-patent literature 1 describes an example of the configuration method of a message authentication code.    Non-patent literature 1: Tetsu Iwata, Kaoru Kurosawa, “OMAC: One-Key CBC MAC”, LNCS 2887 (2003), pp 129-153, Springer-Verlag.